The system and method of the present embodiment relate generally to the scalability of simulations and games, and more specifically, to a scripting language, query processing, and indexing techniques to efficiently execute large numbers of agent scripts, thus providing a framework for simulation/game scalability.
A very important aspect of computer simulations, and in particular in computer games, is the artificial intelligence (AI) of non-player characters (NPCs), know herein also as agents. To create AI in simulations and games, developers or players can create complex, dynamic behavior for a small number of agents, but neither the conventional game engines nor the style of AI programming enables intelligent behavior that scales to a large number of agents. A computer game is a virtual environment where players interact with digital objects or each other for entertainment. Game AI is the system that controls the behavior of NPCs or agents—entities created by the game designer and controlled by the computer. While this system may use classic AI algorithms, game AI includes all routines that control behavior, be they intelligent or not.
Broadly speaking, there have typically been two approaches to improving game AI. The first is to create complicated, detailed, dynamic behavior for a few particularly important NPCs, like the player's arch-nemesis or sidekick. However, this technique can be computationally expensive and labor intensive and not practical for more than a handful of NPCs. The second approach to game AI is to enable interesting but relatively simple behavior for a large number of NPCs. For example, character behavior may be controlled by a simple finite state machine. In the aggregate, even simple game AI can lead to complex emergent behavior, so populating a game world with many NPCs can create compelling gameplay. However, there is a trade-off between having complex NPCs and having many NPCs. When the game demands too many NPCs, developers may have no choice but to employ simple game AI. But if the AI is too simple, the game will exhibit predictable uniformity. This trade-off is not addressed by the classic areas of research in artificial intelligence. A further complication in creating large numbers of NPCs is the actual design of the AI for each NPC. Even if the processing power is available, creating AI is very labor intensive. To solve the problem of content creation, developers employ the use of data-driven AI. In this paradigm, the AI system is heavily parameterized by data files stored outside the code. In the simplest case, these parameters may be numerical values affecting transitions in state machines. However, more generally, they are scripts that are read and processed by the game's AI engine. This approach works for designing large numbers of NPCs because these scripts are simple but flexible enough to be adapted to many kinds of characters. In addition, a data-driven AI scheme offloads much of the burden of creating AI from the programmers to the game designers, allowing the game AI to be modified rapidly without recompiling.
The ability to produce interesting data-driven AI depends on the expressive power of these scripts. In the scripting languages currently used in games, the more expressive the scripting language, the smaller the number of NPCs that can be processed at any given time.
What is needed is a data-driven AI system that is both highly expressive and capable of supporting large numbers of NPCs. A data-driven AI system can separate the game content from the game code. As the number of NPCs with distinct behaviors grows, the maximal complexity of those NPCs must decrease to maintain performance. However, when large numbers of NPCs are making individual decisions, they may be acting on distinct but very similar sets of information. What is further needed is to view game AI as a data management problem to dramatically boost performance.
What is still further needed is a functional scripting language that can allow the analysis of agent scripts written by users and the rewriting of those agent scripts to factor out “expensive” function evaluation. Data base cost models can be used to predict the cost of executing a query plan with and without an index at a certain point. An “expensive” function is one in which the use of an index at a certain point could reduce the cost of its evaluation. Query processing techniques can be used to pre-compute the results of the expensive functions and indexing techniques can be used to quickly access them within the scripts. What is still further needed is a scripting language that is accessible to game designers, for example, by being functionally similar to languages used in existing games. What is even still further needed is that the AI system is designed to operate within a typical game architecture without disrupting the usual structure of the other systems.
Data-driven games typically have similar designs in which three different groups of actors interact with the system, the largest of whom are the game players interacting with the game through the input and display devices. Another group of actors includes the game programmers who have designed the “game engine” which can consist of several different generic components common to all games, such as rendering and audio engines, physics engines, and AI engines. All of these engines can be connected together through a simulation engine which can control actions of the characters and objects, instructing the rendering and audio engines how to generate output. The discrete simulation engine can take cues from the physics and AI engines, but it is largely directed by the content of the game. The game content is created by the game designers. The designers are responsible for creating the game world. This includes a lot of the artistic elements like character models and sounds. However, it also includes any game specific logic. The character objects are stored in data files outside of the game engine. The behavior of these character objects is defined by the character scripts. These scripts are read by either a compiler or an interpreter, and processed by the discrete simulation engine. This separation is particularly important for game AI, as character behavior can be constantly adjusted during game testing for reasons of “game balance” (i.e. ensuring that there is no single optimal strategy, so that game play does not become monotonous). This separation is also important to players, as they can also interact with the content as game “modders”. A modder is player who modifies a commercially released game to create a game variant. Conventional computer games can be architected so that the AI engine processes its objects in clock ticks. In turn-based games, these ticks are controlled by player input; the game will not proceed to the next tick until the player ends his or her turn. In real-time games, these ticks are controlled entirely by the game, and progress proportional to the frame-rate of the graphics engine. Each clock tick, the simulation engine processes the actions of one or more characters. Each character can perform at most one action per tick. What is needed is for the number of NPCs to be determined by the data, and thus to allow more than one unit to act per clock tick. In conventional games, a particular action may span more than a single clock tick, as the game takes time to render the action. However, this is modeled by performing the action in a single tick, and assigning the character a “cooldown” period until it can act again. As a result, some characters may be inactive during a clock tick, as they are still in the cooldown period from their last action. An improvement to this conventional design can be to process, on each clock tick, one action for every character in the game.
Each action, in turn, may produce several effects. An effect can be an update to the data which defines an object. For example, movement is an action that has a single effect—it alters the position of that unit. On the other hand, mortar-fire in a combat game is an action that may affect several units, damaging every NPC in its blast radius. At each clock tick, in a conventional system, the simulation engine can read the data, determine the actions of each of the characters, determine the effects of the actions, and then update the game data for the next tick. It is conventional practice in game design that when multiple characters act during a clock tick, they act simultaneously. Thus the conventional simulation engine may not read the data more than once during a clock tick, as no action can depend on the action of another character in the same tick. Each clock tick can be separated into three stages: a query stage, where the contents of the game data are read, a decision stage, where the actions of each NPC are chosen based on the data read, and an update stage, where the game data are updated according to the effect of these actions. Since the actions can be updating the game data simultaneously, a transaction model is needed for how these updates are processed. Conventional games can separate effects into stackable and nonstackable. In stackable effects, like damage, all of the effects for that tick are cumulative. For nonstackable effects, only one effect of that kind can apply—typically the most beneficial (or disadvantageous, depending on the context). The effects of all the actions can be combined, using sum for stackable effects and max for the nonstackable ones; the data values can be incremented or decremented accordingly. An effect may set some character data to an absolute value. For example, a freeze spell may set a character's speed to 0. In these instances, the effect is given a priority. Thus they are nonstackable effects determined by maximum priority.
What is needed is an expressive language and, with a change in expressiveness, a perceptible (positive) effect on the gameplay. Real-time strategy (RTS) games can be scaled to large numbers of characters. In these games, a player does not control a single character, but instead controls armies of characters, which are called units. The player controls units by selecting them and issuing commands, which they then execute. However, the way in which a unit executes a command is controlled by the game AI. For example, if a human player instructs a character to attack a specific enemy unit, the game AI may first instruct it to attack other nearby enemy units just so that it can maneuver into range. The game play can consist of issuing a command to a unit, and then scrolling to another portion of the map to command other units, while the first unit executes its orders. Thus these games can scale by orders of magnitude without advances in rendering technology. Because of this game play, RTS games can have scripts defining the behavior of each individual. A player wants a unit to execute its command correctly without further instruction; that way the player can issue commands to large numbers of units, effectively controlling massive armies. What is needed is an improvement in unit behavior in RTS games. In conventional RTS games, a player must directly control the units if there is to be any coordination between units. For example, a standard tactic in strategy games is to have archers stay behind armored troops in order to protect them; if the armored troops move, the archers need to move as well to retain their cover. In this case, the human player may have to neglect other troops and repeatedly issue instructions to these two.
Processing individual AI scripts can be very expensive if each unit is processed separately. For example, if the game designer wants a certain type of unit to run in fear from a large number of marching skeletons, and if the number of skeletal troops is on the order of n, the total number of units, then it takes O(n) to count the number of skeletons. Furthermore, if all the units can see the skeletons, then each unit performs an Ω(n) count aggregate, for a total time of Ω(n2) to process all of the units. In conventional RTS games all coordination is handled in centralized AI scripts. In centralized AI, a script controls the actions of a large number of units. For example, each computer player in Warcraft III has two invisible commanders to control all the units: one for attacking, and one for defense. Centralized AI controls units by querying the environment, and then issuing a simple command to each unit. This solves the problem in the skeleton example since the centralized script can count the number of skeletal troops in O(n) time and issue the “run away” instruction to each unit again in O(n) time.
However, centralized AI has three major problems. Because one script controls all of the units of a faction, it is difficult to write scripts that control more than one geographic cluster of units at a time. The limitation of Warcraft III to two commanders means the computer is unable to defend and fight a multiple-front war at the same time; human players use limitations like this to their advantage. Another problem is that it is difficult to separate individual behavior from herd behavior. When the centralized AI script sees the skeletal warrior, it issues the run away command to all units. Thus the units flee uniformly, ignoring issues such as which units can see the skeletons. Changing the centralized script to account for this makes the script harder to design and read. Most importantly, however, centralized AI is designed to run the computer player and not the human player because the human player controls individual units, and not a central commander. Therefore, what are needed are individual AI scripts. What is further needed is a scripting language that allows rewrite rules to group calculations together, which can be processed in a script compiler. What is still further needed is a query language that manages iteration under at least the following circumstances: computing an aggregate value about a set of units or the local environment, for example, summing up the strength of visible units, or finding the weakest unit in range; applying an update to a set of units or the environment; processing an array whose size is fixed and determined at compile time; reimplementing functionality that exists already in the game, but is not open to modders (e.g. the pathfinding algorithms in the AMAI file common.eai). Such a language could be functional and include aggregate functions on sets. At each step, the AI script could perform a declarative query on the environment and use the result to perform an update. Further, the language could take advantage of overlap in actions by the use of indices.
A battle simulation is structured like that of the conventional RTS. The state of each unit can consist of at least three values: the x and y position of the unit, and its health. Health can be modeled as an integer; when it is reduced to 0, the unit is dead and is removed. There can be three types of actions: a unit can move (to change its x and y value), damage an enemy unit (reducing its health), or heal a friendly unit (restoring its health). Which of these actions are available depends on the type of the unit. Knight units can only move and attack. They can be armored, and hence take less damage from the attacks of others. They can also do the most damage in their attacks. However, they can only attack units that are in arm's reach. Archer units can only move and attack. Unlike knights, they are not armored, so they can take more damage from the attacks of others. Their arrows can also do less damage than the swords of the knights. They can have a much larger range in which they damage an enemy unit. Healer units can only move and heal. Like archers, they may not be armored, and so take more damage from the attacks of others. They can heal units by casting a “healing aura” that restores health to all friendly units within the circle of this aura. The health of a unit can never be restored beyond the initial health of the unit. Healing auras can be nonstackable, so a unit can only be healed once per clock tick.